package com.shuo.dsa.niuke;

import com.shuo.dsa.model.TreeNode;

import java.util.Stack;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向
 *      思路: 中序遍历即可
 */
public class TreeToList {

    private TreeNode head;
    private TreeNode pre = null;

    /**
     * 递归版
     */
    public TreeNode ConvertRecur(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        ConvertRecur(pRootOfTree.left);
        pRootOfTree.left = pre;
        if (pre != null)
            pre.right = pRootOfTree;
        pre = pRootOfTree;
        head = head == null ? pRootOfTree : head;
        ConvertRecur(pRootOfTree.right);
        return head;
    }


    /**
     * 非递归版
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = pRootOfTree;
        TreeNode pre = null;
        TreeNode head = null;
        boolean isFirst = true;
        while (temp != null || !stack.isEmpty()) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                temp = stack.pop();
                // 开干: 2个if都是为了处理第一个节点而已
                if (isFirst) {
                    isFirst = false;
                    head = temp;
                }
                if (pre != null)
                    pre.right = temp;
                temp.left = pre;
                pre = temp;
                // 结束
                temp = temp.right;
            }
        }
        return head;
    }
}
